1. Field of the Invention
This invention relates to electronic computer systems, and more particularly to methods and apparatus for processing large images.
2. Description of Related Art
One use of computers is to manipulate graphical images, such as photographs, line drawings, etc. Frequently, such images are too large to fit into memory (as opposed to storage) at once. Accordingly, it is known to break such images into grids of subimages, commonly referred to as image tiles or simply "tiles", and manipulate one or a few tiles at a time within memory, swapping out from storage for other tiles as necessary. A grid of tiles may be of any size N.times.M, including 1.times.M, or N.times.1, in which case each tile is a strip across an image. Tiles can be of any shape that can be used to cover a 2-dimensional area and need not all be the same shape or size. For example, tiles can be hexagons in a "honeycomb" grid. Conventionally, however, rectangular tiles arranged in a regular rectangular grid are used for ease of manipulation.
In conventional implementations, a tiled image is represented by two components: some basic geometric information describing the bounds of the image and the arrangement of the tiles (the tiling geometry), and a tile array containing a tile ID for every tile in the image. A tile array can be any data structure used for mapping a tile index (determined based on the tiling geometry) to a tile ID.
FIG. 1 shows an example of a two-by-two grid of four tiles 2, designated "a", "b", "c", and "d", containing the tile pixel data for the tiled image. Each tile comprises n.times.m pixels. In FIG. 1, tile "a" is in memory, while tiles "b", "c", and "d" (shown as hatched) are in storage. Accordingly, while all four tiles 2 may be required to depict an object 3 in the image, only part of the image would be accessible in memory at any one time. Also shown is a data structure 4 defining the tiled image, comprising a tile array 6, having indices 1, 2, 3, and 4 corresponding to tiles "a", "b", "c", and "d", respectively, based on a data structure 8 defining the tiling geometry. Data structures equivalent to a tile array, such as linked lists, trees, tables, etc., can also be used.
In conventional implementations, tile IDs are mapped to tile control records. This mapping may be based on either a direct address mapping (i.e., the IDs are pointers) or the tile IDs may be indices into another data structure. Tile control records contain whatever information is necessary for tracking the storage location(s) of the tile pixel data for the particular image tile. Thus, tiled images are represented using tile arrays which contain tile IDs which refer to tile control records which lead to tile pixel data.
Returning to the example if FIG. 1, the tile array 6 associated with the tiled image 2 can be used to translate the indices into tile IDs which correspond to particular tile control records which lead to tile pixel data. Under the terms defined above, we can say that the tile array 6 maps index 1 to image tile "a", and mean that the tile array 6 maps index 1 to the tile ID which leads to the tile control record which leads to the tile pixel data for image tile "a". (In FIG. 1, the tile control blocks are represented as merged with the pixel data in large rectangles. The linkages between tile array 6 elements and pixel data are indicated by arrows.)
The mapping from tile IDs to tile control records is injective--i.e., there is at most one tile ID for any given tile control record. (Generally, it is surjective as well, in that tile control records without tile IDs are useless.) The mapping from tile control records to pixel data is also injective in that no two tile control records refer to the same pixel data. Thus, there is essentially a one-to-one correspondence between tile IDs, tile control records, and tile pixel data. We will therefore take the liberty of referring simply to an image tile when we do not care about the individual pieces of this trio.
To find the value for a pixel within an image stored in a tiled representation, the image tile containing the desired pixel must be determined, then the location of the pixel within that tile must be determined. A conventional way for determining the coordinates of a pixel involves the following steps:
1. Determine the index of the tile containing the pixel, based on the pixel's coordinates in the image (this assumes that indices have been assigned to the tiles in the image and that a mapping has been established from coordinates to indices). PA1 2. Translate the index into a reference to the tile containing the desired pixel. PA1 3. Convert the coordinates for the pixel into tile relative coordinates. PA1 4. Use the tile relative coordinates to find the desired pixel in the subimage represented by the tile.
Conventionally, small tiles frequently have a format similar to bitmaps, in which a pixel value can be accessed via simple array indexing. Multiple pixels can be accessed in a similar fashion. The only restriction that a tiled representation places on accessing multiple pixels is that the desired pixels must be broken up into collections of pixels that fit within individual tiles. Other methods of accessing pixels within tiles may be used, such as searching through tiles that include bounds information describing the area each tile covers within the parent image. However, the above-described description is the most conventional implementation for pixel access within a tiled image.
One reason for using image tiles is because memory resources are not sufficient to store an entire image at one time. However, at times it is desirable to have two versions of the same image. For example, if an "undo" function is desired, a first version of an image must be stored while making changes in a second version of the same image, so that the user can "undo" all actions (up to the previous undo) by simply reverting to the unchanged source image. Having a single level of "undo" requires either sufficient memory to store two versions of an image, or requires that one image be stored on a storage device while the "new" version is maintained in memory. In either case, a copying operation must be undertaken, in which data comprising the source "pre-undo" image is copied to a target image, with all the attendant data structures (including tile array) being generated for the target image. Such copying takes not only memory resources, but time, particularly with large images.
Accordingly, it would be desirable if an improved system existed for providing an easy means for "undoing" an operation on a user-perceived image, while conserving use of memory and storage. The present invention provides such a system that includes other benefits as well.